package heapsort;
/**
 * er zit een kleine fout in. (namens goolkate).
 * de fout zit in de heap en zal waarschijnlijk liggen in het wegschrijven van de juiste getallen
 * na mate je grotere getallen gaat toepassen wordt de uitvoer beter
 * 
 * @author Ken Veensta
 *
 */

public class Sorter {

	private Reader r;
	private Writer w;
	private int[] heap;
	private int tmp;
	private int pos;
	private static int generatedNumbers = 1000;
	private int theHeap = 50;

	public static void main(String[] args) {
		Generator g = new Generator( generatedNumbers );
		Sorter s = new Sorter();
	}

	public Sorter() {
		r = new Reader( "heapsort100.txt" );
		w = new Writer();
		heap = new int[ theHeap ]; //heaps

		int oude = 0;

		for (int i = 0; i < heap.length - 1; i++) {
			heap[i] = r.getOneInt();
		}

		heap = heapsort(heap);
		pos = heap.length - 1;

		while (!r.empty()) {
			w.writeInt(heap[0]);
			oude = heap[0];
			heap[0] = r.getOneInt();

			if (heap[0] > oude) {
				heapsort(heap, pos);
			} else {
				exchange(0, pos);
				pos--;
				heapsort(heap, pos);

				if (pos == 0) {
					heapsort(heap);
					pos = heap.length - 1;
					w.writeSpace();
				}
			}
		}

		for (int i = 0; i < heap.length - 1; i++) {
			if (i != pos) {
				System.out.println("Rest heap");
				w.writeInt(heap[i]);
				heapsort(heap, pos);
			} else {
				System.out.println("Rest deadspace");
				w.writeInt(heap[i]);
				w.writeSpace();
				heapsort(pos);
				pos = heap.length - 1;
			}
		}

		w.close();
		System.out.println("Writer closed.");
		r.close();
		System.out.println("Reader closed.");
		System.out.println("Aantal runs: " + w.getTeller());
		System.out.println("Aantal getallen: " + r.getTeller());
		System.out.println("Gem run Lengte: " + ((float) r.getTeller() / (float) w.getTeller()));
	}

	public int[] heapsort(int[] tempHeap) {
		for (int i = tempHeap.length / 2; i >= 0; i--) {
			percDown(tempHeap, i, tempHeap.length);
		}

		for (int i = tempHeap.length - 1; i > 0; i--) {
			swapReferences(tempHeap, 0, i);
			percDown(tempHeap, 0, i);
		}
		return tempHeap;
	}

	public int[] heapsort(int[] tempHeap, int goTo) {
		for (int i = goTo / 2; i >= 0; i--) {
			percDown(tempHeap, i, tempHeap.length);
		}

		for (int i = goTo; i > 0; i--) {
			swapReferences(tempHeap, 0, i);
			percDown(tempHeap, 0, i);
		}
		return tempHeap;
	}

	public int[] heapsort(int through) {
		int[] a = heap;
		for (int i = through / 2; i >= 0; i--) {
			percDown(a, i, a.length);
		}

		for (int i = through; i > 0; i--) {
			swapReferences(a, 0, i);
			percDown(a, 0, i);
		}
		return a;
	}

	private int leftChild(int i) {
		return 2 * i + 1;
	}

	private void percDown(int[] tempHeap, int i, int heapLength) {
		int child;

		for (tmp = tempHeap[i]; leftChild(i) < heapLength; i = child) {
			child = leftChild(i);
			if (child != heapLength - 1 && tempHeap[child] - (tempHeap[child + 1]) < 0)
				child++;
			if (tmp - (tempHeap[child]) < 0)
				tempHeap[i] = tempHeap[child];
			else
				break;
		}
		tempHeap[i] = tmp;
	}

	public void exchange(int i, int j) {
		int v;
		v = heap[i];
		heap[i] = heap[j];
		heap[j] = v;
	}

	public void swapReferences(int[] tempHeap, int index1, int index2) {
		int tmp = tempHeap[index1];
		tempHeap[index1] = tempHeap[index2];
		tempHeap[index2] = tmp;
	}

}